package leetcode
//641. 设计循环双端队列
type MyCircularDeque struct {
	queue []int
	head,tail int
	length int
}


func Constructor2(k int) MyCircularDeque {
	return MyCircularDeque{
		queue:  make([]int, k+2),
		head:   0,
		tail:   1,
		length: k+2,
	}
}


func (this *MyCircularDeque) InsertFront(value int) bool {
	if this.IsFull(){
		return false
	}
	this.queue[this.head]=value
	this.head=(this.head+this.length-1)%this.length
	return true
}


func (this *MyCircularDeque) InsertLast(value int) bool {
	if this.IsFull(){
		return false
	}
	this.queue[this.tail]=value
	this.tail=(this.tail+1)%this.length
	return true
}


func (this *MyCircularDeque) DeleteFront() bool {
	if this.IsEmpty(){
		return false
	}
	this.head=(this.head+1)%this.length
	return true
}


func (this *MyCircularDeque) DeleteLast() bool {
	if this.IsEmpty(){
		return false
	}
	this.tail=(this.tail+this.length-1)%this.length
	return true
}


func (this *MyCircularDeque) GetFront() int {
	if this.IsEmpty(){
		return -1
	}
	return this.queue[(this.head+1)%this.length]
}


func (this *MyCircularDeque) GetRear() int {
	if this.IsEmpty(){
		return -1
	}
	return this.queue[(this.tail+this.length-1)%this.length]
}


func (this *MyCircularDeque) IsEmpty() bool {
	if (this.head+1)%this.length==this.tail{
		return true
	}
	return false
}


func (this *MyCircularDeque) IsFull() bool {
	if (this.tail+1)%this.length==this.head{
		return true
	}
	return false
}
//239. 滑动窗口最大值，用单调队列
func maxSlidingWindow(nums []int, k int) []int {
	//队列保持单调递减，因为index小且值小的数字会被后面大的给覆盖
	q:=make([]int,0)
	for i:=0;i<k;i++{
		for len(q)>0&&nums[q[len(q)-1]]<nums[i]{
			q=q[:len(q)-1]
		}
		q=append(q, i)
	}
	ans:=make([]int,0)
	ans=append(ans, nums[q[0]])
	for i:=k;i<len(nums);i++{
		for len(q)>0&&nums[q[len(q)-1]]<nums[i]{
			q=q[:len(q)-1]
		}
		q=append(q, i)
		if i-q[0]+1>k{
			q=q[1:]
		}
		ans=append(ans,nums[q[0]])
	}
	return ans
}

